package LeetCodeP;

/**
 * T一条包含字母 A-Z 的消息通过以下方式进行了编码：
 *
 * 'A' -> 1
 * 'B' -> 2
 * ...
 * 'Z' -> 26
 * 给定一个只包含数字的非空字符串，请计算解码方法的总数。
 *
 * 示例 1:
 *
 * 输入: "12"
 * 输出: 2
 * 解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。
 * 示例 2:
 *
 * 输入: "226"
 * 输出: 3
 * 解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/decode-ways
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author long
 * @date 2020-03-23 20:49
 */
public class Soluction91 {

    public static  int numDecodings(String s) {
        if(s.charAt(0)=='0'){
            return 0;
        }
        char[] chars=s.toCharArray();
        return decode(chars,chars.length-1);
    }

    //字符串转换成字符数组，利用递归函数decode ，从最后一个字符向前递归。
    public static int decode(char[] chars,int index){
        //处理得到的第一个字符，只能有一种解码方式，返回 1
        if (index<=0){
            return 1;
        }
        int count=0;
        char curr=chars[index];
        char prev=chars[index-1];
        // 当前字符比 “0” 大，则直接利用它之前的字符串所求得的结果
        if (curr>'0'){
            count=decode(chars,index-1);
        }
        //由前一个字符和当前字符所构成的数字，值必须要在 1 到 26 之间，否则无法进行解码 
        if (prev=='1'||(prev=='2'&&curr<='6')){
            count+=decode(chars,index-2);
        }
        return count;

    }

    public static  void  main(String[] args){
            String s="226";
        int i = numDecodings(s);
        System.out.println(i);
    }

}
